package com.togo.algorithm.easy.search;

/**
 * @Author taiyn
 * @Description 统计一个数字在排序数组中出现的次数。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: 2
 * 示例 2:
 * <p>
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: 0
 *  
 * <p>
 * 提示：
 * <p>
 * 0 <= nums.length <= 105
 * -109 <= nums[i] <= 109
 * nums 是一个非递减数组
 * -109 <= target <= 109
 * @Date 11:32 AM 2023/5/25
 **/
public class Offer53 {

    public int searchTraversal(int[] nums, int target) {

        int count = 0;
        for (int i : nums) {
            if (i == target) count++;
        }

        return count;
    }

    public int search(int[] nums, int target) {

        int count = 0;
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int v = nums[mid];
            if (v == target) {
                count++;
                int c = mid;
                mid++;
                while (mid >= 0 && mid <= nums.length - 1) {

                    if (nums[mid] == target) {
                        count++;
                        mid++;
                    } else break;
                }
                mid = c;
                mid--;
                while (mid >= 0 && mid <= nums.length - 1) {
                    if (nums[mid] == target) {
                        count++;
                        mid--;
                    } else break;
                }
                break;
            } else if (v > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }

        }

        return count;
    }

    public static void main(String[] args) {

        int[] nums = {5, 7, 7, 8, 8, 10};
        int target = 8;

        Offer53 offer53 = new Offer53();
        System.out.println(offer53.search(nums, target));
    }
}
